package com.company.algo.niuke;

import java.util.HashMap;
import java.util.Map;

/** 【做过又不会的】
 * 最长无重复子数组-阿里
 * 给定一个数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
 * 子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
 * 输入 [2,2,3,4,8,99,3]
 * 输出 5，最长子数组为[2,3,4,8,99]
 * 哈希set+双指针，维护一个滑动窗口
 */
public class LongestNonRepeatingSubarray {
    public int maxLength1(int[] arr) {
        if (arr.length <= 1) return arr.length;
        int l = 0, r = 0;
        Map<Integer, Integer> map = new HashMap();
        int res = 0;
        while (r < arr.length) {
            if (map.containsKey(arr[r])) {
                l  = Math.max(l,map.get(arr[r])+1);
            }
            map.put(arr[r], r);
            res = Math.max(res, r - l + 1);
            r++;
        }
        return res;
    }
    //可以只用维护左指针，右指针直接通过for循环不断右移即可
    public int maxLength(int[] arr) {
        if (arr.length == 0) return 0;
        int res = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0, j = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])){
                j = Math.max(j,map.get(arr[i])+1);
            }
            map.put(arr[i],i);
            res = Math.max(res,i-j+1);
        }
        return res;
    }


    public static void main(String[] args) {
        LongestNonRepeatingSubarray Main = new LongestNonRepeatingSubarray();
        int[] arr = {3, 3, 2, 1, 3, 3, 3, 1};
        System.out.println(Main.maxLength(arr));
    }
}
